1. Field
This disclosure relates to compression of halftoned images, more particularly to a method and system that use the halftone screen and image statistics to predict the binary pattern.
2. Background
Digital printers render images and text by producing dots of ink of color, one color in a monochrome system or several colors in a color system. The human eye blurs these dots together, which produces the images xe2x80x98seenxe2x80x99 by the brain. Images of continuous tone (contone) such as photographs do not have dots in them, so they must be converted using a process referred to as halftoning. Halftoning produces the mix of dot values that the eye will interpret as contone images.
Halftoning is performed by applying a screen to the image, breaking it into a series of dots. Recently, frequency modulation (FM) or blue noise screens have been applied to images. They result in pleasing halftoning results, with smooth tone scale and computational simplicity. However, they can result in some problems when compressing halftone images.
For example, U.S. Pat. No. 4,193,096, issued Mar. 11, 1980, discloses a method for encoding and decoding a half-tone image. However, the compression relies upon a correlation between quadrants of the image, and the quadrants are very small. FM screens tend to be too large for techniques such as this, as well as having the effect of decorrelating the data. This will make any predictions based upon neighboring pixels or regions of the image inaccurate.
Similarly, U.S. Pat. No. 4,760,460, issued Jul. 26, 1988, discloses a method for transmission of halftone images. This method relies upon a dither matrix of 16 levels and requires some spatial correlation in order to function effectively. Most FM or blue noise screens have 256 levels, making this inadequate for images to which these screens are applied. Additionally, the random nature of these screens also limits any spatial correlation, making this an ineffective method. These same problems occur with other techniques, such as those disclosed in U.S. Pat. No. 4,965,677, issued Oct. 23, 1990. This technique also assumes some sort of spatial correlation. In this instance, the spatial correlation needed is in the vertical dimension of the image.
An approach that does not necessarily rely upon spatial correlation can be found in U.S. Pat. No. 5,859,931, issued Jan. 12, 1999. It applies to halftoned images to which error diffusion has been applied and relies upon a limited number of neighboring pixels for prediction of dot values. The encoding is run-length encoding, which also serves to reduce its requirements for spatially correlated data. However, the approach used is extremely computationally intensive, requiring more time or a very powerful processor to perform its tasks.
None of the approaches neither above, nor similar examples, allow for efficient compression of halftoned images utilizing FM screens. In some instances, attempts to apply these techniques to image data actually result in an expansion rather than a compression of the image data. A need exists for a method that allows these images to be compressed and transferred across a network or stored with low bandwidth or memory requirements.
One embodiment of the invention is a method for compression and decompression of halftoned images using the halftone screen. The compression method reduces an input binary image into a mean image, uses the halftone screen in combination with the mean image to produce a predicted image. The predicted image is then compared to the original image to produce a residue image. The residue image and the mean image are then compressed and either stored or transmitted. For decompression, the mean image and residue image are decompressed and then used with the halftone screen to arrive at a reconstructed binary image. A prediction process uses the mean image and scales it to a full-size image that has substantially similar dimensions as the original image. It then applies the halftone screen to the full-size image and produces a predicted image.